% PDP
% ordinamenti liste in prolog
% 
% Francesco Cotto

%Verifica lista ordinata

is_sorted([]).
is_sorted([_]).
is_sorted([X,Y|T]) :- X=<Y , is_sorted([Y|T]).



%InsertSort (basato su accumulatore)

insert_sort(List,Sorted) :- i_sort(List,[],Sorted).

%i_sort(lista da ordinare, Accumulatore, Nuovo Accomulatore)
%una lista vuota e' ordinata.
i_sort([],Acc,Acc).  %unificazione da Acc a Sorted
%semplice scorrimento della list da ordinare (H si inserisce in Acc ottenendo un NewAcc)
i_sort([H|T],Acc,Sorted) :- insert(H,Acc,NAcc),i_sort(T,NAcc,Sorted).

%inserimento ordinato  (crescente)
%insert(Elemento da inserire, Lista in cui inserire elemento, Lista con elemento inserito)
insert(X,[Y|T],[Y|NT]) :- X>Y,insert(X,T,NT).
insert(X,[Y|T],[X,Y|T]) :- X=<Y.
insert(X,[],[X]).


%BubbleSort

bubble_sort(List,Sorted) :- b_sort(List,[],Sorted).
%bsort(lista da ordinare, accumulatore che viene costruito, lista ordinata da restituire)
b_sort([],Acc,Acc).  %unificazione da Acc a Sorted
%scorri la lista (chiamata ricorsiva) mettendo in accumulatore il massimo della sottolista
b_sort([H|T],Acc,Sorted) :- bubble(H,T,NT,Max),b_sort(NT,[Max|Acc],Sorted).
   
%bubble(elemento da confrontare,
%       sottolista con cui confrontare elemento,
%       nuova sottolista senza il massimo ma con il minore tra l'emento da confrontre e head della sottolista
%       massimo della sottolista tra elemnto)
% Ossia con bubble si ottiene il massimo tra una sottolista e un elemento, e una nuova sottolista (priva del massimo)
bubble(X,[],[],X). %unificazione per ottenere il massimo della sottolista
%elemento X e il maggiore, il confronto continua sulla sottolista rimasti
bubble(X,[Y|T],[Y|NT],Max) :- X>Y,bubble(X,T,NT,Max).
%X non e il maggiore, si continua il confronto usando Y come elemento da confrontare, e mettendo X nella nuova sottolista
bubble(X,[Y|T],[X|NT],Max) :- X=<Y,bubble(Y,T,NT,Max).


%MergeSort

merge_sort([],[]).     % una lista vuota e gia ordinata 
merge_sort([X],[X]).   % lista con un solo elemento e gia ordinata
merge_sort(List,Sorted) :-
    List=[_,_|_],divide(List,L1,L2),     % lista con almeno due elementi viene divisa e poi si applica ricorsivamente ordinamento:
        merge_sort(L1,Sorted1),merge_sort(L2,Sorted2),  % ogni parte e ordinata
        merge(Sorted1,Sorted2,Sorted).                  % poi merge delle parti

%merge(Lista1, Lista2, Mergedelleliste)
merge([],L,L).
merge(L,[],L) :- L\=[]. %il corpo della regola serve a evitare una ricorsione infinita tra i 2 merge "di fine ricorsione".
merge([X|T1],[Y|T2],[X|T]) :- X=<Y,merge(T1,[Y|T2],T).
merge([X|T1],[Y|T2],[Y|T]) :- X>Y,merge([X|T1],T2,T).


%Divisione array per MergeSort, ovvero
%Come dividere una lista in due? ... halve

halve(L,A,B):-hv(L,[],A,B).

%hv(lista da dividere, accumulatore per sottolista B, sottolista A, sottolista B)
%B si ottiene da quel che rimane dalla lista da dividere
hv(L,L,[],L).      % per liste di lunghezza pari
hv(L,[_|L],[],L).  % per liste di lunghezza dispari
hv([H|T],Acc,[H|L],B):-hv(T,[_|Acc],L,B).

%divisione: uno a testa (pari/dispari)
pd(L,A,B) :- p(L, A, B).

p([],[],[]).
p([H|T],[H|A],B) :- d(T, A,B).
d([],[],[]).
d([H|T],A,[H|B]) :- p(T, A, B).

%stesso principio pari dispari ma "concentrato" (si inverte odd e even tra testa e corpo)
pd2([],[],[]).
pd2([H|T],E,[H|O]):-pd2(T,O,E).

divide(L,L1,L2):-halve(L,L1,L2).


%QuickSort
quick_sort([],[]).
quick_sort([H|T],Sorted):-
        pivoting(H,T,L1,L2),quick_sort(L1,Sorted1),quick_sort(L2,Sorted2),
        append(Sorted1,[H|Sorted2], Sorted).

%pivotinc(H elemento di pivot, lista da dividere, lista < H, lista > H)
pivoting(_,[],[],[]).
pivoting(H,[X|T],[X|L],G):-X=<H,pivoting(H,T,L,G).
pivoting(H,[X|T],L,[X|G]):-X>H,pivoting(H,T,L,G).
